import java.util.*;

public class Solution373 {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans=new ArrayList<>();
        Queue<int[]> queue=new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int i=0;i<nums1.length;i++){
            queue.offer(new int[]{nums1[i]+nums2[0],i,0});
        }
        while (!queue.isEmpty() && ans.size()<k){
            int[] temp=queue.poll();
            if (temp[2]!=nums2.length-1){
                queue.offer(new int[]{nums1[temp[1]]+nums2[temp[2]+1],temp[1],temp[2]+1});
            }
            List<Integer> l=new ArrayList<>();
            l.add(nums1[temp[1]]);
            l.add(nums2[temp[2]]);
            ans.add(l);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution373().kSmallestPairs(new int[]{1,2},new int[]{3},3));
    }
}
